import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/19 14:34
 * @description DFS
 */
public class Solution2 {
    public static void main(String[] args) {

    }

    private int m;
    private int n;
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        m = grid.length;
        n = grid[0].length;

        int land = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    // 找到第一个陆地，dfs
                    land++;
                    dfs(grid, i, j);
                }
            }
        }
        return land;
    }
    public void dfs(char[][] grid, int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {
            // 超过边界或碰到水，返回
            return;
        }
        // 访问过的陆地，置为0，防止重复访问
        grid[i][j] = '0';
        // DFS四个位置相邻位置
        dfs(grid, i-1, j);
        dfs(grid, i, j+1);
        dfs(grid, i+1, j);
        dfs(grid, i, j-1);
    }
}
